package com.gitee.feizns.explore.data_structure.tree.bs.easy;

/**
 * @author feizns
 * @since 2020/1/4
 */
public class IsSubtree {

    public static void main(String[] args) {
        TreeNode node = create();
        System.out.println(isSubtree(node, node.right.right.right.right));
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(1);
        ret.right = new TreeNode(1);
        ret.right.right = new TreeNode(1);
        ret.right.right.right = new TreeNode(1);
        ret.right.right.right.right = new TreeNode(1);
        ret.right.right.right.right.right = new TreeNode(1);
        ret.right.right.right.right.right.right = new TreeNode(1);
        ret.right.right.right.right.right.right.right = new TreeNode(1);
        ret.right.right.right.right.right.right.right.right = new TreeNode(1);
        ret.right.right.right.right.right.right.right.right.right = new TreeNode(1);
        ret.right.right.right.right.right.right.right.right.right.right = new TreeNode(1);
        ret.right.right.right.right.right.right.right.right.right.right.left = new TreeNode(2);
        return ret;
    }

    private static TreeNode createT() {
        TreeNode ret = new TreeNode(4);
        ret.left = new TreeNode(1);
        ret.right = new TreeNode(2);
        return ret;
    }

    public static boolean isSubtree(TreeNode s, TreeNode t) {
        if ( s != null )
            return equals(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
        return t == null;
    }

    private static boolean equals(TreeNode s, TreeNode t) {
        if ( s == null && t == null )
            return true;
        if ( s != null && t != null && s.val == t.val )
            return equals(s.left, t.left) && equals(s.right, t.right);
        return false;
    }

}
